package indi.zn.commons.tree;

import java.text.Collator;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.collect.Lists;

/**
 * @author: 周楠
 * @param <I>
 * @param <V>
 * @date 2016年6月8日 上午10:44:09
 */

@SuppressWarnings("rawtypes")
public class TreeFactory {
	
	private static Logger log=LoggerFactory.getLogger("TreeFactory");
	
	
	private static class Count{
		
		public  Integer count=new Integer(1); 
		
		public void plus(){
			count=count+1;
		}
		
	}


	private static<I> int compareNode(TreeNode<I> o1, TreeNode<I> o2) {

		int res = 0;

		if (o1.getPid().getClass().getName().equals(Integer.class.getName())) {

			Integer o1pid = (Integer) o1.getPid();
			Integer o2pid = (Integer) o2.getNid();

			res = Integer.compare(o1pid, o2pid);

		} else if (o1.getPid().getClass().getName()
				.equals(String.class.getName())) {
			String o1pid = (String) o1.getPid();
			String o2pid = (String) o2.getNid();
			res = Collator.getInstance().compare(o1pid, o2pid);
		} else if (o1.getPid().getClass().getName()
				.equals(Long.class.getName())) {
			Long o1pid = (Long) o1.getPid();
			Long o2pid = (Long) o2.getNid();
			res = Long.compare(o1pid, o2pid);
		}

		return res;

	}

	public static<I,N extends TreeNode<I>> Tree<I,TreeNode<I>> generateTree(TreeNode<I> root,
			List<? extends TreeNode<I>> nodelist) {
		
		
		
		Collections.sort(nodelist,new TreeNode.NodeComparator());

		if(log.isDebugEnabled()){
		for (TreeNode<I> treeNode : nodelist) {
			log.debug(treeNode.getNid()+" / "+ treeNode.getPid());		
		}
		}
		
		
		Count nodeconut = new Count();

		
		List<Integer> levels = new ArrayList<>();

		find(root, nodelist, 0, nodeconut, levels);

		Tree<I,TreeNode<I>> tree = new Tree<>(root, 1);

		Collections.sort(levels);

		int max = levels.size() > 1 ? levels.get(levels.size() - 1) : 0;

		tree.setMaxlevel(max);

		tree.setNodecount(nodeconut.count);

		return tree;

	}

	@SuppressWarnings("unchecked")
	private static <I> void find(TreeNode<I> root, List<? extends TreeNode<I>> nodelist,
			int l, Count count, List<Integer> levels) {

		int low = 0;
		int high = nodelist.size() - 1;

		while (low <= high) {

			int mid = (high - low) / 2 + low;

			TreeNode n = nodelist.get(mid);
			
			if (n.getPid().equals(root.getNid())) {

				int c = innerFind(root, n, nodelist, mid, l, count, levels);

				levels.add(c);

				break;
				
				

			} else if (compareNode(n, root) == 1) {

				high = mid - 1;

			} else if (compareNode(n, root) == -1) {

				low = mid + 1;

			}

		}

	}

	@SuppressWarnings("unchecked")
	private static <I> int innerFind(TreeNode fnode, TreeNode n,
			List<? extends TreeNode<I>> nodelist, int mid, int l, Count count,
			List<Integer> levels) {

		
		if(fnode.getChildrenNodes()==null) {
		
			fnode.setChildrenNodes(Lists.newArrayList());
			
		}
		
		fnode.getChildrenNodes().add(n);

		n.setParentNode(fnode);
			

		l++;

		count.plus();;

		find(n, nodelist, l, count, levels);  //子节点 进入查找

		for (int i = 1; i < nodelist.size(); i++) {

			int f = mid + i;
			
			
			log.debug("n_h:" +f );
		
			if (f >= nodelist.size())
				break;

			TreeNode n_h = nodelist.get(f);

			if (n_h.getPid().equals(fnode.getNid())) {

				fnode.getChildrenNodes().add(n_h);

				n_h.setParentNode(fnode);
				
				log.debug("n_h find: "+n_h.getPid()+" / "+ fnode.getNid());	
				
				count.plus();;
				find(n_h, nodelist, l, count, levels);

			} else {

				break;

			}

		}

		for (int i = 1; i < nodelist.size(); i++) {       

			int f = mid - i;
						
			log.debug("n_l:" +f );

			if (f < 0)
				break;

			TreeNode n_l = nodelist.get(f);

			if (n_l.getPid().equals(fnode.getNid())) {

				fnode.getChildrenNodes().add(n_l);
				n_l.setParentNode(fnode);
				
				log.debug("n_l find: "+n_l.getPid()+" / "+ fnode.getNid());					
				count.plus();
				find(n_l, nodelist, l, count, levels);

			} else {

				break;

			}

		}
		return l;

	}

}
